package nachos.threads;

import nachos.machine.*;
import java.util.Vector;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {

	/**
	 * Allocate a new priority scheduler.
	 */
	public PriorityScheduler() {
	}

	/**
	 * Allocate a new priority thread queue.
	 *
	 * @param	transferPriority	<tt>true</tt> if this queue should
	 *					transfer priority from waiting threads
	 *					to the owning thread.
	 * @return	a new priority thread queue.
	 */
	public ThreadQueue newThreadQueue(boolean transferPriority) {
		return new PriorityQueue(transferPriority);
	}

	public int getPriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getPriority();
	}

	public int getEffectivePriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getEffectivePriority();
	}

	public void setPriority(KThread thread, int priority) {
		Lib.assertTrue(Machine.interrupt().disabled());

		Lib.assertTrue(priority >= priorityMinimum
			&& priority <= priorityMaximum);

		getThreadState(thread).setPriority(priority);
	}

	public boolean increasePriority() {
		boolean intStatus = Machine.interrupt().disable();

		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if (priority == priorityMaximum) {
			return false;
		}

		setPriority(thread, priority + 1);

		Machine.interrupt().restore(intStatus);
		return true;
	}

	public boolean decreasePriority() {
		boolean intStatus = Machine.interrupt().disable();

		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if (priority == priorityMinimum) {
			return false;
		}

		setPriority(thread, priority - 1);

		Machine.interrupt().restore(intStatus);
		return true;
	}
	/**
	 * The default priority for a new thread. Do not change this value.
	 */
	public static final int priorityDefault = 1;
	/**
	 * The minimum priority that a thread can have. Do not change this value.
	 */
	public static final int priorityMinimum = 0;
	/**
	 * The maximum priority that a thread can have. Do not change this value.
	 */
	public static final int priorityMaximum = 7;

	/**
	 * Return the scheduling state of the specified thread.
	 *
	 * @param	thread	the thread whose scheduling state to return.
	 * @return	the scheduling state of the specified thread.
	 */
	protected ThreadState getThreadState(KThread thread) {
		if (thread.schedulingState == null) {
			thread.schedulingState = new ThreadState(thread);
		}

		return (ThreadState) thread.schedulingState;
	}

	/**
	 * A <tt>ThreadQueue</tt> that sorts threads by priority.
	 */
	protected class PriorityQueue extends ThreadQueue {

		PriorityQueue(boolean transferPriority) {
			this.transferPriority = transferPriority;
			queue = new java.util.PriorityQueue<ThreadState>();
		}

		/*
		 * "thread" needs to wait in line, tell it where to stand
		 */
		public void waitForAccess(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());
			resetAll();
			getThreadState(thread).waitForAccess(this);
			resetQueue();
		}

		/*
		 * its "thread"'s turn, tell it to go
		 */
		public void acquire(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());
			resetAll();
			getThreadState(thread).acquire(this);
			resetQueue();
		}

		/*
		 * return the next thread in line.  remove it from the line as well
		 */
		public KThread nextThread() {
			Lib.assertTrue(Machine.interrupt().disabled());
			if (owner != null) {
				owner.acquired.remove(this);
			}
			ThreadState ts = queue.poll();
			if (ts == null) {
				return null;
			}
			acquire(ts.thread);
			owner = ts;
			return ts.thread;
		}

		/**
		 * Return the next thread that <tt>nextThread()</tt> would return,
		 * without modifying the state of this queue.
		 *
		 * @return	the next thread that <tt>nextThread()</tt> would
		 *		return.
		 */
		protected ThreadState pickNextThread() {
			if (queue.isEmpty()) {
				return null;
			}
			return queue.peek();
		}

		public void print() {
			Lib.assertTrue(Machine.interrupt().disabled());
			System.out.println("!-------------------------------------!");
			System.out.println("Contents of Queue");
			for (ThreadState st : queue) {
				if (st != null) {
					System.out.println("\t" + st.thread.getName() + ": " + st.priority + " - " + st.getEffectivePriority() + " - " + st.thread.status);
				}
			}
			System.out.println(queue.isEmpty());
			System.out.println("!-------------------------------------!");
		}

		public void resetAll() {
			for (ThreadState st : queue) {
				st.resetPriority();
			}
		}

		public void resetQueue() {
			java.util.PriorityQueue<ThreadState> temp = new java.util.PriorityQueue<ThreadState>();
			for (ThreadState st : queue) {
				st.primeComparator(transferPriority);
				temp.add(st);
			}
			queue = temp;
		}
		/**
		 * <tt>true</tt> if this queue should transfer priority from waiting
		 * threads to the owning thread.
		 */
		public boolean transferPriority;
		public java.util.PriorityQueue<ThreadState> queue; //what threads are waiting in line (ordered by priority)
		public ThreadState owner;
	}

	/**
	 * The scheduling state of a thread. This should include the thread's
	 * priority, its effective priority, any objects it owns, and the queue
	 * it's waiting for, if any.
	 *
	 * @see	nachos.threads.KThread#schedulingState
	 */
	protected class ThreadState implements Comparable<ThreadState> {

		/**
		 * Allocate a new <tt>ThreadState</tt> object and associate it with the
		 * specified thread.
		 *
		 * @param	thread	the thread this state belongs to.
		 */
		public ThreadState(KThread thread) {
			this.thread = thread;
			acquired = new Vector();
			acquired.add((PriorityQueue) thread.waitqueue);
			setPriority(priorityDefault);
			resetPriority();
			epriority = priority;
			refresh = false;
		}

		/**
		 * Return the priority of the associated thread.
		 *
		 * @return	the priority of the associated thread.
		 */
		public int getPriority() {
			return priority;
		}

		/**
		 * Return the effective priority of the associated thread.
		 *
		 * @return	the effective priority of the associated thread.
		 */
		public int getEffectivePriority() {
			System.out.println(thread.getName() + "----------" + acquired.size());
			if (!refresh) {
				int tPrior;
				ThreadState t;
				for (PriorityQueue tq : acquired) {
					if (tq.transferPriority) {
						t = tq.pickNextThread();
						if (t != null && t != this) {
							tPrior = tq.pickNextThread().getEffectivePriority();
							if (tPrior > epriority) {
								epriority = tPrior;
							}
						}
					}
				}
			}
			refresh = true;
			return epriority;
		}

		public int compareTo(ThreadState o) {
			if (comparatorPriming) {
				return o.getEffectivePriority() - getEffectivePriority();
			}
			return o.getPriority() - getPriority();
		}

		public void resetPriority() {
			epriority = priority;
			refresh = false;
		}

		/**
		 * Set the priority of the associated thread to the specified value.
		 *
		 * @param	priority	the new priority.
		 */
		public void setPriority(int priority) {
			if (this.priority == priority) {
				return;
			}
			epriority = priority;
			this.priority = priority;
			resetPriority();
		}

		/**
		 * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
		 * the associated thread) is invoked on the specified priority queue.
		 * The associated thread is therefore waiting for access to the
		 * resource guarded by <tt>waitQueue</tt>. This method is only called
		 * if the associated thread cannot immediately obtain access.
		 *
		 * @param	waitQueue	the queue that the associated thread is
		 *				now waiting on.
		 *
		 * @see	nachos.threads.ThreadQueue#waitForAccess
		 */
		public void waitForAccess(PriorityQueue waitQueue) {
			comparatorPriming = waitQueue.transferPriority;
			waitQueue.queue.add(this);
		}

		public void primeComparator(boolean set) {
			comparatorPriming = set;
		}

		/**
		 * Called when the associated thread has acquired access to whatever is
		 * guarded by <tt>waitQueue</tt>. This can occur either as a result of
		 * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
		 * <tt>thread</tt> is the associated thread), or as a result of
		 * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
		 *
		 * @see	nachos.threads.ThreadQueue#acquire
		 * @see	nachos.threads.ThreadQueue#nextThread
		 */
		public void acquire(PriorityQueue waitQueue) {
			acquired.add(waitQueue);
		}
		/** The thread with which this object is associated. */
		protected KThread thread;
		/** The priority of the associated thread. */
		protected int priority;
		protected int epriority;
		boolean refresh;
		boolean comparatorPriming;
		//a list to hold threads that are waiting on this thread
		protected Vector<PriorityQueue> acquired;
	}
}
